1. Field of the Invention
This invention relates to figure location detecting systems which detect positional relationships between figures to be matched with each other. This application is based on patent application No. Hei 9-83351 filed in Japan, the content of which is incorporated herein by reference.
2. Prior Art
Conventionally, there is provided technology to detect a positional relationship between figures, in other words, technology to perform detection as to which location (or part) of a second figure a first figure matches with. This technology is used for the figure matching devices which perform the matching process with respect to fingerprints and aerial photographs.
For example, the paper of Japanese Patent Laid-Open Publication No. 5-181949 (denoted by "paper 1") discloses an image positioning device corresponding to one example of the above technology conventionally known. According to this, an airplane equipped with a photographing machine flies over some terrestrial areas to take geomorphologic pictures, from which a matched picture being subjected to the matching process with another picture is obtained. Then, the device detects a positional correspondence between positional coordinates of the matched picture and the map coordinates which are determined in advance.
In the conventional system, characteristic points are extracted from the matched picture and are subjected to affine transformation using an affine coefficient which is set in advance. Thus, the matched picture is transformed to conform with the map coordinate system. The point pattern matching is performed between "matching" characteristic points, which are used as reference for the matching process (or pattern matching), and matched characteristic points which are obtained by the affine transformation of the characteristic points to conform with the map coordinate system. Thus, it is possible to provide matching characteristic point pair candidates through the point pattern matching. Thereafter, the system performs processes similar to the aforementioned processes with respect to each of matching cases while changing the affine coefficient by a prescribed interval of value. Those processes are repeated until the affine coefficient, which is changed every time the processes are performed with respect to each of the matching cases, becomes out of a prescribed range. When execution of the processes is ended because the affine coefficient becomes out of the prescribed range, the conventional system selects a matching case that a number of the matching characteristic point pair candidates is the largest from among the aforementioned matching cases. Coordinates values of the matching characteristic point pair candidates in the selected matching case are placed into a transformation equation representing a coordinate relationship between two figures. Thus, the system produces a coefficient of the above transformation equation.
According to the conventional technology described above, the matched picture corresponds to an aerial photograph taken by the photographing machine whose dip and photographing direction are roughly determined in advance. In other words, the conventional technology is not designed in consideration of the situation where the direction of the matched picture is uncertain. So, the conventional technology is inapplicable to the situation where the direction of the matched picture is uncertain. In addition, the conventional technology handles the whole area of the matched picture by using single affine transformation. So, the conventional technology is inapplicable to the situation where the matched picture is partially distorted. Further, the conventional technology is designed such that the coordinate values of the matching characteristic point pair candidates are placed into the transformation equation to produce the coefficient of the transformation equation. So, if an error is included in the matching characteristic point pair candidates which are used to produce the coefficient of the transformation equation, there is a high risk that the produced coefficient of the transformation equation becomes incorrect.
Meanwhile, the fingerprint matching technology introduces a concept in definition of the center of the fingerprint pattern. The conventional technology uses such a concept to match characteristic points of a search fingerprint with characteristic points of a file fingerprint with respect to the coordinates system. One example of this technology is disclosed by the paper (denoted by "paper 2") of the monographic journal of the Institute of Electronics, Information and Communication Engineers of Japan, Volume J72-DII, No. 5, pp. 733-740 issued on May of 1989, for example. However, this technology is inapplicable to the picture, such as the palm print, which does not contain a pattern which can be defined as the center.
The paper of Japanese Patent Publication No. 63-21232 (denoted by "paper 3") discloses another example of the above technology.
According to the above, the system finds out the characteristic point of the search fingerprint and the characteristic point of the file fingerprint, which are similar each other with respect to an amount of local characteristics. Those characteristic points are connected with each other as a matching characteristic point pair candidate. Then, the system calculates a similarity score for the above matching characteristic point pair candidate. Incidentally, an amount of local characteristics is defined by the kind(s) of the characteristic points or a number of characteristic points which exist within a certain radius range of the figure. Suppose a local coordinate system that the characteristic point is used as an origin of the coordinates while the direction of the characteristic point is represented by a Y axis. Herein, an amount of local characteristics is defined by a number of other characteristic points which are distributed in each of quadrants of the local coordinate system or a number of ridge lines which intervene between the characteristic point in each quadrant of the local coordinate system and its closest characteristic point.
Thereafter, the system rotates the search fingerprint by a certain angle of rotation. Then, the following processes are performed with respect to each characteristic point of the rotated search fingerprint, as follows:
The system selects one of the characteristic points of the rotated search fingerprint. The file fingerprint has characteristic points, one of which is connected with the above characteristic point selected by the system. So, the system calculates differences between X, Y coordinates values of the selected characteristic point and X, Y coordinates values of the connected characteristic point of the file fingerprint. Being connected with the differences, the system records a similarity score calculated for a pair of the above characteristic points on a recording media. Thereafter, the system selects another characteristic point from among the characteristic points of the search fingerprint which are not selected. So, the system performs processes similar to the foregoing processes on the newly selected characteristic point. In this case, the system calculates differences with regard to the newly selected characteristic point. If the differences newly calculated exist in the pre-calculated differences which have been already calculated, a similarity score calculated for a pair of characteristic points is accumulated with the similarity score which has been already recorded with being connected with the pre-calculated differences. The above processes are repeatedly performed with respect to all of the characteristic points of the search fingerprint. Thereafter, the system selects a highest similarity score (i.e., maximum weighting factor) from among the similarity scores which are recorded. In addition, the system calculates differences which are connected to the highest similarity scores. So, the system records the maximum weighting factor and differences on a recording media.
Next, the system rotates the search fingerprint again. So, the system performs processes similar to the foregoing processes with respect to the rotated search fingerprint. Thus, the system calculates a maximum weighting factor as well as differences which are connected to the maximum weighting factor with respect to the rotated search fingerprint. Then, the system compares the "present" maximum weighting factor which is presently calculated with the "previous" maximum weighting factor which has been previously calculated but which remains now. Only when the present maximum weighting factor is greater than the previous maximum weighting factor, the system renews recorded values with values corresponding to the differences and maximum weighting factor which are presently calculated.
By repeating the foregoing processes, it is possible to obtain a rotation angle of the search fingerprint which makes the maximum weighting factor to be really maximal as well as differences regarding X, Y coordinates values. The above rotation angle is used as a best rotation angle that establishes a best matching state between the characteristic points of the search fingerprint and the characteristic points of the file fingerprint. In addition, the differences which are calculated with respect to the above rotation angle are used as an amount of parallel displacement (or parallel translation).
In short, the conventional technology described above performs calculations and matching processes while rotating the search fingerprint, which is a searched picture subjected to search, by a certain angle, so it produces differences regarding X, Y coordinates values with respect to a certain rotation angle of the search fingerprint that makes the maximum weighting factor to be really maximal. The above rotation angle and differences are used as the best rotation angle and parallel displacement respectively, which establish a best matching state between the characteristic points of the search fingerprint and the characteristic points of the file fingerprint. Thus, this technology is applicable to the picture whose direction is uncertain and the picture which does not have a pattern defining the center. In addition, this technology is applicable to the situation where a wrong matching characteristic point pair candidate is included in the matching characteristic point pair candidates.
The aforementioned paper 3 does not at all provide a concrete description as to the method (or technique) how to obtain the matching characteristic point pair candidates between the characteristic points of the searched picture and the characteristic points of the file picture. According to the technology described in the paper 3, even if the system selects wrong matching characteristic point pair candidates which are wrongly proposed to some extent, the system is capable of producing "correct" coordinate matching parameters (i.e., rotation angle and parallel displacement). However, if the system selects a number of wrong matching characteristic point pair candidates, there is a high risk that the system produces "incorrect" coordinate matching parameters. In general, when there exist a plenty of characteristic points whose characteristics are similar each other within the searched picture, a risk that the system selects a plenty of wrong matching characteristic point pair candidates becomes higher. So, the foregoing conventional technology must suffer from an increased risk that incorrect coordinate matching parameters are produced when a plenty of characteristic points whose characteristics are similar each other exist within the searched picture. In addition, the above technology is not designed in consideration of the situation where the searched picture contains distortion. So, when using the distorted picture (or partially distorted picture) as the searched picture, the conventional technology suffers from a problem that incorrect coordinate matching parameters are produced.